#斐波那契数列
#方法一：
def f(n,mem={}):
    if n<=1:
        return 1
    else:
        if n-1 in mem:
            a=mem[n-1]
        else:
            a=f(n-1)
            mem[n-1]=a
        if n-2 in mem:
            b=mem[n-2]
        else:
            b=f(n-2)
            mem[n-2]=b
        c=a+b
        return c
print(f(5))

#方法二：递归
def fab(n):
    if n<=1:
        return 1
    else:
        return fab(n-1) + fab(n-2)
print(fab(5))